dp

public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        int max = 1;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
}


public int lengthOfLIS2(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        LinkedList<Integer> slow = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            int ele = nums[i];
            if (slow.isEmpty() || ele > slow.getLast()) {
                slow.add(ele);
            } else {
                int idx = binarySearchLargerEleIndex(slow, ele);
                slow.set(idx, ele);
            }
        }

        return slow.size();
    }

    private int binarySearchLargerEleIndex(LinkedList<Integer> low, int val) {
        int left = 0;
        int right = low.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int ele = low.get(mid);
            if (ele < val) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    

#include <iostream>
using namespace std;
int i,j,n,s,t,a[100001];
int main()
{
    cin>>n;
    a[0]=-1000000;
    for(i=0;i<n;i++)
    {
        cin>>t;
        if(t>a[s]) a[++s]=t;
        else
        {
            int l=1,h=s,m;
            while(l<=h)
            {
                m=(l+h)/2;
                if(t>a[m]) l=m+1;
                else h=m-1;
            }
            a[l]=t;
        }
    }
    cout<<s<<endl;
}

解法1
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-increasing-subsequence/solutions/147667/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/


解法2
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-increasing-subsequence/solutions/147667/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/


这道题的方法二，原题解写的不太容易理解，试着在这里再解释一遍：

无序列表最关键的一句在于： 数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值，即在数组 1,2,3,4,5,6中长度为3的上升子序列可以为 1,2,3也可以为 2,3,4等等但是d[3]=3，即子序列末尾元素最小为3。
数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值
数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值
数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值

无序列表解释清了数组d的含义之后，我们接着需要证明数组d具有单调性，即证明i<j时，d[i]<d[j]，使用反证法，假设存在k<j时，d[k]>d[j]，但在长度为j，末尾元素为d[j]的子序列A中，将后j-i个元素减掉，可以得到一个长度为i的子序列B，其末尾元素t1必然小于d[j]（因为在子序列A中，t1的位置上在d[j]的后面），而我们假设数组d必须符合表示长度为 i 的最长上升子序列的末尾元素的最小值，此时长度为i的子序列的末尾元素t1<d[j]<d[k]，即t1<d[k]，所以d[k]不是最小的，与题设相矛盾，因此可以证明其单调性

无序列表证明单调性有两个好处：1.可以使用二分法；2.数组d的长度即为最长子序列的长度；

（大家如果觉得有帮助，麻烦点个赞，顶我上去，让更多的人看到~）

我们举一个原始序列为{1,3,5,2,4,6,7,0}的例子来模拟下这个过程：

初始slow = []
nums[0] = 1，于是slow = [1]
nums[1] = 3，于是slow = [1, 3]
nums[2] = 5，于是slow = [1, 3, 5]
nums[3] = 2，2替换3，于是slow = [1, 2, 5]
nums[4] = 4，4替换5，于是slow = [1, 2, 4]
nums[5] = 6，于是slow = [1, 2, 4, 6]
nums[6] = 7，于是slow = [1, 2, 4, 6, 7]
nums[7] = 0，0替换1,于是slow = [0, 2, 4, 6, 7]
LIS的长度 = slow的长度 = 5

我们最后发现slow的长度为LIS的长度，但是slow列表明显不是一个LIS，甚至它都不是一个子序列。在nums[7] = 0这一步破坏了子序列的性质，这里的slow列表在于记录最小序列，代表了一种“最可能性”，只是此种算法为计算LIS而进行的一种替换。
